/*
	Richard Acosta
	March 10, 2008
	Recursive Decent Parcer - C++
	
	Grammar:
		E -> T + E | T - E | T
		T -> P * T | P / T | P
		P -> I | (E)
		I -> a | b | ... | y | z
	
*/
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool matchE(string);
bool matchT(string);
bool matchP(string);
bool matchI(string);
void strSplit(string, string, vector<string> &);

int main() {
	string input;
	cout << "Input a string to test: ";
	cin >> input;
	if(matchE(input)) {
		cout << input << " is part of the language.\n\n";
	} else {
		cout << input << " is not part of the language.\n\n";
	}

	system("pause");
	return 0;
}

bool matchE(string input) { // T + E | T - E | T

	vector<string> temp;

	temp.clear();
	strSplit(input, "+", temp);
	if(temp.size() == 2 && matchT(temp[0]) && matchE(temp[1])) {
		return true;
	}

	temp.clear();
	strSplit(input, "-", temp);
	if(temp.size() == 2 && matchT(temp[0]) && matchE(temp[1])) {
		return true;
	}

	if(matchT(input)) {
		return true;
	}

	return false;
}

bool matchT(string input) { // P * T | P / T | P
	
	vector<string> temp;

	temp.clear();
	strSplit(input, "*", temp);
	if(temp.size() == 2 && matchP(temp[0]) && matchT(temp[1])) {
		return true;
	}

	temp.clear();
	strSplit(input, "/", temp);
	if(temp.size() == 2 && matchP(temp[0]) && matchT(temp[1])) {
		return true;
	}

	if(matchP(input)) {
		return true;
	}

	return false;
}

bool matchP(string input) { // I | (E)
	if(matchI(input))
		return true;

	if(input.length() >= 3 && input[0] == '(' && input[input.length()-1] == ')') {
		if(matchE(input.substr(1,input.length() - 2))) {
			return true;
		}
	}
	return false;
}

bool matchI(string input) {
	if(input.length() == 1 && input[0] >= 'a' && input[0] <= 'z') { // a b c ... z
		return true;
	}
	return false;
}

void strSplit(string str, string delim, vector<string> &parts) {
	int foundAt;
	foundAt = str.find_first_of(delim);

	if(foundAt == string::npos)
		return;

	parts.push_back(str.substr(0,foundAt));
	parts.push_back(str.substr(foundAt + 1));
	return;
}


